/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-06
 * Time: 20:15
 */
public class Solution {
    // 动态规划, 背包问题
    public int cuttingRope(int n) {
        // 因为 至少要切割成两段
        if (n <= 3) {
            return n-1;
        }
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int i = 1;i <= n;i++) {
            // 取 Max (以 i 结尾的这段绳子 * 这段绳子之前的最大值 )
            for (int j = i-1;j >= 0;j--) {
                dp[i] = Math.max(dp[i], (i-j)*dp[j]);
            }
        }
        return dp[n];
    }



    class Solution2 {
        public int cuttingRope(int n) {
            if (n <= 3) {
                return n-1;
            }
            int ans = 1;
            while (n > 4) {
                ans *= 3;
                n -= 3;
            }
            return ans*n;
        }
    }
}
